package uestc.lj.basic.graph;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 宽度遍历图
 *
 * @Author:Crazlee
 * @Date:2021/11/24
 */
public class Code01_BFS {
	/**
	 * 宽度优先遍历
	 *
	 * @param node 给定图中的一个节点
	 */
	public static void bfs(Node node) {
		if (node == null) {
			return;
		}
		// 队列用来进行BFS宽度优先遍历
		Queue<Node> queue = new LinkedList<>();
		// set用来标记节点是否访问过
		HashSet<Node> set = new HashSet<>();

		queue.add(node);
		set.add(node);

		while (!queue.isEmpty()) {
			Node cur = queue.poll();
			System.out.print(cur.value);
			// 遍历从本节点出发可达到的节点bfs
			for (Node next : cur.nexts) {
				//未曾访问过就入队
				if (!set.contains(next)) {
					set.add(next);
					queue.add(next);
				}
			}
		}
	}
}
